Academic Open Internet Journal

www.acadjournal.com

Volume 13, 2004

 

A New design and Performance evaluation of Congestion Based Dynamic TCP Send Buffer Allocation

 

Ramachandra V. Pujeri 1          S. N. Sivanandam2

1Assistant Professor, 2Professor and Head

Department of Computer Science and Engineering

PSG College of Technology, Coimbatore-641 004, India.

E-mail: sriramu_vp@yahoo.com

 

ABSTRACT

The network has grown in to a powerful tool in the recent past. The good utilization of resources can cause an immense change in server’s performance. One such valuable resource, which should be optimized, is the TCP Send Buffer[4]. Conventional methods of allocating send buffer waste a lot of server resources and are also inefficient, as they do not consider certain important factors which affect the utilization of the network. The CBD or Congestion Based Dynamic algorithm[5] proposed here tries to achieve an efficient use of the send buffer. It takes into account the important parameters of the transmission such as RTT send rate, maximum buffer size on the receiver’s side. In this algorithm, we set a functional value for each request and the buffer is allocated proportionately. To accomplish this we divide the send buffer space of the server into two segments. The Experimental Segment allocates send buffer for the new entrants temporarily and some time later the request will be swapped to the Processing Segment. This algorithm is capable of handling critical conditions such as congestion, ill-behaved clients since this algorithm is based on the function, which allows congestion control through a passive system such as a send buffer.

 

Keyword: TCP Send Buffer, Experimental Segment, Processing Segment, Implicit Congestion control, Round Trip Time.

 

1. Introduction:

            Networking as all of us know is a very powerful & growing field. Using server’s resources to maximum is still a challenge. To optimize the use of server’s resources we have taken up the send buffer allocation. This area has been ignored but the results one could actually get by optimizing them are far too good to be left alone. Before proceeding further, the brushing up the following is required.

            TCP/IP is a set of protocols developed to allow cooperating computers to share resources across a network. As with all other communications protocol, TCP/IP is composed of layers: IP is responsible for moving packet of data from node to node. IP forwards each packet based on a four-byte destination address (the IP number). The Internet authorities assign ranges of numbers to different organizations. The organizations assign groups of their numbers to departments. IP operates on gateway machines that move data from department to organization to region and then around the world. TCP - is responsible for verifying the correct delivery of data from client to server. Data can be lost in the intermediate network. TCP adds support to detect errors or lost data and to trigger retransmission until the data is correctly and completely received. 

            RTT is an acronym for Round Trip Time; it is a measure of the time it takes for a packet to travel from a computer, across a network to another computer, and back. The sending side records the clock when it transmits a packet, and then examines the clock again when an acknowledgment arrives. By subtracting the two values, it obtains a single estimate of the round trip time. It then combines that single estimate with previous estimates to get an average.

            In a typical HTTP server, the major components of the main memory are the operating system kernel, the server processes and a file cache. An important part of the kernel space is dedicated to network buffers that are mainly employed by the server as TCP send-buffers. In a common HTTP session, the server copies the requested data to the TCP send-buffer. From there, the data is forwarded to the client by the output routines of the TCP stack. When the requested data is larger than the send-buffer size, this procedure is repeated until the whole transfer is completed.

1.2 Conventional methods and its demerits:

            The conventional methods used to allocate TCP send buffer were static in the sense that they did not analyze the various factors that affect the connectivity. They were allocating server resources without taking into account the Congestion, RTT, send rate, loss probability, etc. and hence a lot of server’s resources were wasted. Those connections, which never required so much resource, were provided with resources, which were ultimately useless, and the connections that needed a lot more resources were seen on par with other connections.

            Treating a leased line connection on par with a 56 Kbps modem and allocating equal resources to them really wastes server resources.  High bandwidth connections are made to lose their benefit of having a large bandwidth just because of improper allocation policy.

1.3 Proposed method:

            To overcome the disadvantages of the conventional methods, in this paper we consider the some parameters of the network like RTT, Loss Probability, Send Rate etc to allocate buffer dynamically. We relate send rate with RTT and loss probability to derive a function which is used to derive the Functional Value, whose derivation is as given below. We allocate the minimum of Wmax/RTT and the calculated space required based on Functional Value, since the maximum data that can be sent cannot exceed the former value. Congestion is controlled to a greater extent implicitly since the allocated buffer is in accordance with RTT and send rate. Performance of our algorithm and the current algorithm is done later in this paper.

 

 

3. Algorithm Description (Mathematical Model):

i.          The Experimental / Processing segment ratio is calculated on the

              following property of connectivity

                        a.         Frequent and Short duration: More Experimental Segment.

                        b.         Less frequent and Longer duration: Less Experimental Segment.

                        In both the cases, the amount of Processing Segment is greater than    the Experimental Segment.

ii.  ExptPktNum is calculated initially for the allocation of buffer to the new entrant. It is determined on an experimental basis and it varies with each server. It depends upon the average no. of connections or requests to the server.

iii.                In case of space insufficiency for a new request in Experimental Segment, message is sent to all requests for the possible decrease in their allocation.

a.   In case a positive acknowledgement is received then their allocated buffer is diminished by a predefined Sacrifice Percent and the new request is allocated if sufficient space is available in Experimental Segment

b. Otherwise, the new request is put into the Waiting Queue.

iv.                 Calculate RTT, Receiver’s buffer size and Loss Probability for every new request.

v.                   Calculate Functional Value and allocate buffer for each request on the basis of the derivation given in the previous section.

vi.                 If the calculated request space is greater than the free space, then allocate to the possible extent and put the remaining requirement into the Need List.

vii.               Revise the calculated buffer size as before, after periodic intervals of Refresh rates which depend upon the network and reallocate buffer for each request.

viii.             Incase of an entry in the Need List of Processing Segment, go to Step 6.

ix.                 On exit, free the allocated space of the process.

3.1 CBD Algorithm:

3.1.1 Predetermined Constant Parameters:

Segments                  :           Experimental, Processing

SendBufferSize         :           Contains the maximum Processing Segment size

                                                // Depends on the server used

RefreshRate              :           Periodic time of calculation of parameters

                                                // Depends on the server used

ExptPktNum               :           Number of Experimental Packets sent initially

// Depends of the ratio of Experiment:Processing segment ratio.

//Experimental Segment: Processing segment ratio is n : m (n > m, always)

//This is also depends the application for which the server is used for.

3.1.2 Variable Parameters:

SendRatesum                  :           Summation of Send Rates of all Current processes

Allocated                    :           A List containing the size of the allocated resources

Need                           :           A List containing further need of a Process

FreeSpace                :           Contains free space size of Processing Segment.

LossProb                   :           Probability of Packet Loss for a process

B[1:n]                          :           Send Rate of Processes

RTTi                            :           Round Trip Time of ith Process

3.1.3 Procedures used:

Procedure ReviseParameters (Process P)

Procedure AcceptRequest (Process CurrentProcess)

Procedure ReviseBuffAllocated (Process P)

 

 

 

3.2. algorithm:

// Whenever new Request arrives…                      

Begin

If (There is a request from client) Then      

            // Check whether the memory is available in the reserved segment.

            If (MemoryAvailable (Experimental) =True) Then 

                        //Accept the request

            Jump RequestAccepted                 

            Else

                        Send Messages to all requests to limit their requirements

                        For all Clients do

// Positive Response for the sent message from the client.

                                    If (Ack [Client] = 1) Then

                                        FreeSpace = FreeSpace + (SacrificePercent * Allotted [Client])

                                          Move on to next Client

                        // Negative Response for the sent message

                                    Else

                                          Move on to next Client

                                    EndIf

                        End For

//   Space Available in Expt Segment

                        If (FreeSpace >= ExptPktNum) Then

                                    Jump RequestAccepted

                        // Not Enough Space

                        Else                                                   

                                    AddWaitingQ (Child: Process)

                                    Jump OnRefresh

EndIf

            EndIf

EndIf

RequestAccepted:

// Calculate all parameters of the new request

Call AcceptRequest (Child: Process)

// Allocate the Buffer in Processing Segment

Call MoveProcessingSegment ()

OnRefresh:

// Recalculate Functional Value on every Refresh rate

            Call ReviseParameters (Process)

            Call ReviseBuffAllocated (Process)

// Check in Need List

If (NotEmpty (NeedList)) Then

            Process NeedList Requirements

EndIf

// Process Requests in Waiting Queue

If (NotEmpty (WaitingQ)) Then

Jump Begin (Child)

EndIf

// A Process wants to Exit

If (Depart (Child: Process))

            FreeSpace = FreeSpace + Allocated [Process]

            SendRatesum  = SendRatesum – SendRateprocess

EndIf

// On the Arrival of a new Request

If (New Client Arrives) Then

            Jump Begin

EndIf

End

// To Calculate parameters with Experimental Packets

Procedure AcceptRequest (Process CurrentProcess)

Begin

            Load Experimental Packets into ExptSegment

            // Calculating RTT and p

Counter: = 0

            Until (All Packets are sent)

            Begin

                        If (TimeExpiry = TRUE)         // Tackling Congestion at Expt Segment

                                    Put the Process into WaitingQ

                        End If

Calculate RTTnew

                                RTTsum = RTTsum + RTTnew

                                Increment Counter    

            End

            // Calculate Average RTT and LossProb

                        RTTavg   = RTTsum / Counter 

 LossProb = 1 – (No. Of Ack / Total No. of Packets)

B [CurrentProcess] = SendRate (CurrentProcess);

SendRatesum   =  SendRatesum + B [CurrentProcess]

//Calculate Space Requested based on Functional Value

RequestSpace = (B [CurrentProcess] / SendRatesum ) * SendBufferSize

RequestSpace = Min {RequestSpace, (Wmax / RTTavg)}

If (RequestSpace < FreeSpace)

                        Allotted [CurrentProcess] = RequestSpace

Else

                        Allotted [CurrentProcess] = FreeSpace

//Add Current Process to Need List to be Allocated Later

Need = RequestSpace - Allotted [CurrentProcess]

End If

End

//Adjust Parameters to Current Situation

Procedure ReviseParameters (Process P)

Begin

            Calculate RTTNew, LossProb

RTTCurrent = (RTTavg + RTTNew  ) / 2

LossProb Current = (LossProb avg + LossProb New  ) / 2

End

//Adjust Allocated BufferSpace

Procedure ReviseBuffAllocated (Process P)

Begin

SendRatesum   = SendRatesum - B [CurrentProcess]

B [CurrentProcess] = SendRate (CurrentProcess);

SendRatesum   =  SendRatesum  + B [CurrentProcess]

//Calculate Space Requested based on Functional Value

RequestSpace = (B [CurrentProcess] / SendRatesum ) * SendBufferSize

RequestSpace = Min {RequestSpace, (Wmax / RTTavg)}

If (RequestSpace < FreeSpace)

                        Allotted [CurrentProcess] = RequestSpace

Else

                        Allotted [CurrentProcess] = FreeSpace

//Add Current Process to Need List to be Allocated Later

Need = RequestSpace - Allotted [CurrentProcess]

End If

End

4. SIMULATION OF THE ALGORITHM AND INFERENCES:

 

In the conventional system the allocation is not dynamic. This implies that all the request independent of its send rate. Thus the same amount of buffer is allocated to all requests. This makes the current allocation algorithm to be inefficient. In our algorithm we deal with send rate mainly. This makes this algorithm more dynamic and powerful.

Fig 4.1 Simulation output

 

From the above simulation we can note that
  1. The space allocated to Process 1 is distributed to other process (e.g. Process 2) after the process 1 ends. This does not happen in the static allocation.
  2. Also we can note that Processes 3 and 4 does not get their extra allocation because they are limited by the Wmax / RTT constraint, which is mentioned in the above derivation.  This helps the server from allocating all the resources to the first set of requests made when a server is switched on and from some ILL-behaved clients who request for more space. This is not provided by the static allocation methods.
  3. Also, it is worth to mention the most important thing we noticed in our experiments. Process 2 faces congestion at some point. Then in static allocation method this is ignored and the same amount of space is allocated to those requests which are affected by traffic and to those which are not. In our algorithm it can be easily noticed that the allocation for Process 2 is decreased and the amount decreased is allocated to other process present in the next refresh. From Inference 2, above, we can understand why the space from 2 is not allocated to Process 3.
  4. Also it is worth mentioning that if we decrease the allocation of the Process 2 to a much lower level than what it requests, then it would have to wait for the more packets which could reduce its send rate thereby freeing traffic a little bit. Thus our algorithm can be used to control congestion, which is not possible in the static algorithm since the current algorithm is not based on send rate.

Though a lot of calculation has to be made, which might decrease the speed of the system, we hope that this algorithm could suit our network because it has a lot of features than the original algorithm. Also with further research it is possible to reduce this derivation to an equivalent but simple formula, which is easy to work.

5. CONCLUSIONS AND SCOPE:

This algorithm controls congestion, by considering the parameters such as RTT, Loss Probability and Send Rate. During Space insufficiency, the new requests are handled properly using Waiting queue. ILL-behaved clients who ask for more space are restricted to maximum allocation using proper techniques.  It is more efficient in allocating the resources to all processes without concentrating more on a specific process. It can be implemented with very few changes in the server protocol. More dynamic as it is based on the network parameters, as the values are revised for every refresh time. But more calculations involved during allocation but can be quickened by using more proper derivation. Future work is required to improving the derivation by decreasing the number of calculations and introducing a simple derivation which will be in order of (RTT/Square root (loss probability)) and inclusion of priority to requests.

 

6. REFERENCES:

 [1]  L. S. Brakmo and L. L. Peterson. TCP Vegas: End to end congestion avoidance  on a global internet. IEEE Journal on Selected Areas in Communications, 13(8):1465{1480, October 1995.

[2] Garth Gibson David A.Patterson and Randy H. Katz. A case for redundant arrays of Inexpensive disks (RAID). In Proceedings of the 1988 ACM conference on Management of Data (SIGMOD).

[3] S. Floyd. TCP and explicit congestion notification. ACM Computer Communication Review, 24(5):10{23, October 1994.

[4] J. Mahdavi J. Semke and M. Mathis. Automatic TCP buffer tuning. Computer Communication Review, 28(4), October 1998.

[5] V. Jacobson, R. T. Braden, and D. A. Borman. TCP extensions for high performance. Technical report, RFC 1323, May 1992.

[6] R. Jain, D. Chiu, and W. Hawe. A quantative measure of fairness and discrimination for resource allocation in shared computer systems. Technical Report TR-301, DEC Research Report, Sept. 1984.

[7] S. McCanne and S. Floyd. NS Network Simulator. http://www-nrg.ee.lbl.gov/ns, 1995.

[8] G. R. Wright and W. R. Stevens. TCP/IP Illustrated: The Implementation, volume 2. Addison-Wesley Publishing Company, 1995.

[9] J. Padhye, V. Firoiu, D. Towsley and J. Kurose, "Modeling TCP Throughput: A Simple Model and its Empirical Validation," Proccedings of SIGCOMM'98.

[10]  Jitendra D. Padhye, Towards a Comprehensive Congestion Control Framework for Continuous Media Flows in Best Effort Networks, March 6, 2000.

 



Technical College - Bourgas,

All rights reserved, © March, 2000